package com.mlick.a.leetcode;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.TimeUnit;

/**
 * @author lixiangxin
 * @date 2019/3/22 10:05
 **/
public class A22 {

  // 1 ()
  // 2 ()()
  //   (())
  // 3 ()()()
  //   (())()
  //   ()(())
  //   (()())
  // 4 ()()()()
  //   (())()()
  //   ()(())()
  //   ()()(())
  //   (()())()
  //   ()(()())
  //   (()()())

  public static void main(String[] args) {
    System.out.println(new Solution1().generateParenthesis(4));
    System.out.println(new Solution2().generateParenthesis(4));
    System.out.println(new Solution3().generateParenthesis(4));

  }


  static class Solution1 {
    public List<String> generateParenthesis(int n) {
      List<String> combinations = new ArrayList();
      generateAll(new char[2 * n], 0, combinations);
      return combinations;
    }

    public void generateAll(char[] current, int pos, List<String> result) {
      if (pos == current.length) {
        if (valid(current))
          result.add(new String(current));
      } else {
        current[pos] = '(';
        generateAll(current, pos + 1, result);
        current[pos] = ')';
        generateAll(current, pos + 1, result);
      }
    }

    public boolean valid(char[] current) {
      int balance = 0;
      for (char c : current) {
        if (c == '(') balance++;
        else balance--;
        if (balance < 0) return false;
      }
      return (balance == 0);
    }
  }

  static class Solution2 {
    public List<String> generateParenthesis(int n) {
      List<String> ans = new ArrayList();
      backtrack(ans, "", 0, 0, n);
      return ans;
    }

    public void backtrack(List<String> ans, String cur, int open, int close, int max) {
      if (cur.length() == max * 2) {
        ans.add(cur);
        return;
      }

      if (open < max)
        backtrack(ans, cur + "(", open + 1, close, max);
      if (close < open)
        backtrack(ans, cur + ")", open, close + 1, max);
    }
  }

  static class Solution3 {
    public List<String> generateParenthesis(int n) {
      List<String> ans = new ArrayList();
      if (n == 0) {
        ans.add("");
      } else {
        for (int c = 0; c < n; ++c) {
          for (String left : generateParenthesis(c)) {
//            System.out.println("c=>" + c + "=>" + left);
            for (String right : generateParenthesis(n - 1 - c)) {
//              System.out.println("n - 1 - c=>" + (n - 1 - c) + "=>" + "(" + left + ")" + right);
              ans.add("(" + left + ")" + right);
            }
          }
        }
      }
      return ans;
    }

    public static void main(String[] args) throws InterruptedException {
//      List<String> strings = new Solution3().generateParenthesis(10);
//      System.out.println(strings);

      for (int i = 0; i < 11; i++) {
        String s = i * 10 + "%";
        System.out.print(getBackslash(s.length()) + s);
        TimeUnit.SECONDS.sleep(1);
      }
      System.out.print("\r");
      System.out.println("finish");
    }

    private static String getBackslash(int length) {

      StringBuilder sb = new StringBuilder();
      for (int i = 0; i < length; i++) {
        sb.append("\b");
      }
      return sb.toString();
    }
  }

}
